package com.shiguiwu.springmybatis.algorithm.tree;

import lombok.Data;

/**
 * @description: 线索化二叉树
 * @author: stone
 * @date: Created by 2022/12/11 15:18
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.tree
 */
public class ThreadedBinaryTree {


    public static void main(String[] args) {
        //创建节点树

        //线索化

        //验证线索化正确性，取某个节点做代表
    }

    private Node root;

    //为了实现前序节点，需要定义一个当前节点的1前序节点指针
    private Node per;


    /**
     * 编写对二叉树的中序线索化
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(Node node) {
        //当前节点null,无法线索化
        if (null == node) {
            return;
        }

        //1，先线索化左子树
        this.threadedNode(node.left);

        //2，线索化当前节点

        //2.1，处理当前节点的前序节点
        if (node.left == null) {
            //遍历到第一个的时候，前序是null的，所以这里null也没有毛病
            node.left = per;
            node.leftType = 1;
        }
        //2.2，处理当前节点的后继节点，后继节点需要下一次遍历的时候处理】
        //有点不好理解
        if (per != null && node.right == null) {
            //让前序节点的右指针指向当前节点
            per.right = node;

            //修改类型
            per.rightType = 1;
        }

        //todo 2.2非常重要，每处理完一个节点之后，让当前节点是下一个节点的前序节点！！！！
        per = node;


        //3，线索化右子树
        this.threadedNode(node.right);

    }







    @Data
    public static class Node {
        private int no;

        private String name;

        private Node left;

        private Node right;

        /**
         * 规定
         * leftType，type 0 就表示作指针指向左子节点，1表示之前前驱节点
         *
         *
         * rightType 就表示作指针指向右子节点，1表示之前后继节点
         */
        private byte leftType = 0;

        private byte rightType = 0;



        public Node(int no, String name) {
            this.no = no;
            this.name = name;
        }

        //前序遍历
        public void preOrder() {
            //先输出父节点
            System.out.println(this);
            //左子树
            if (this.left != null) {
                this.left.preOrder();
            }

            //右子树
            if (this.right != null) {
                this.right.preOrder();
            }


        }

        /**
         * 中序遍历
         */
        public void midOrder() {
            //左子树
            if (this.left != null) {
                this.left.midOrder();

            }
            //输出当前节点
            System.out.println(this);

            //遍历右子树
            if (this.right != null) {
                this.right.midOrder();
            }
        }

        //后序遍历
        public void postOrder() {
            //左子树
            if (this.left != null) {
                this.left.postOrder();

            }

            //遍历右子树
            if (this.right != null) {
                this.right.postOrder();
            }
            //输出当前节点
            System.out.println(this);


        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }


    }
}
